package features.advance.leetcode.math.easy;

/**
 *  剑指 Offer II 001. 整数除法
 *
 *  难度：简单
 *
 * 给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。
 *
 *
 *
 * 注意：
 *
 * 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
 * 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31, 2^31−1]。本题中，如果除法结果溢出，则返回 2^31 − 1
 *
 *
 * 示例 1：
 *
 * 输入：a = 15, b = 2
 * 输出：7
 * 解释：15/2 = truncate(7.5) = 7
 * 示例 2：
 *
 * 输入：a = 7, b = -3
 * 输出：-2
 * 解释：7/-3 = truncate(-2.33333..) = -2
 * 示例 3：
 *
 * 输入：a = 0, b = 1
 * 输出：0
 * 示例 4：
 *
 * 输入：a = 1, b = 1
 * 输出：1
 *
 *
 * 提示:
 *
 * -2^31 <= a, b <= 2^31 - 1
 * b != 0
 *
 *
 * 注意：本题与主站 29 题相同：https://leetcode-cn.com/problems/divide-two-integers/
 *
 * @author LIN
 * @date 2021-08-30
 */
public class Offer2_001 {

    public static void main(String[] args) {
        Solution solution = new Solution() {
        };
        int dividend = Integer.MIN_VALUE;
        int divisor = 1;
        int divide = solution.divide(dividend, divisor);
        System.out.println(divide);
    }

    static class Solution {
        public int divide(int dividend, int divisor) {
            //特殊情况-2^31/-1 会溢出
            if(dividend == 0x80000000 && divisor == -1) {
                return Integer.MAX_VALUE;
            }
            int negative = 2;
            if(dividend > 0){
                negative--;
                dividend = -dividend;
            }
            if(divisor > 0){
                negative--;
                divisor = -divisor;
            }
            int result = 0;
            while (dividend <= divisor){
                int quotient = 1;
                int value = divisor;

                while(value > 0xc0000000 && dividend <= value+value){
                    quotient+=quotient;
                    value+=value;
                }
                result += quotient;
                dividend -=value;
            }

            return negative == 1 ? -result :result;
        }
    }
}
